//重排链表
//测试链接 https://leetcode.cn/problems/reorder-list/
public class ReorderList {

    public class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    public void reorderList(ListNode head) {
        // 处理边界情况
        if (head == null || head.next == null || head.next.next == null)
            return;
        // 1. 找链表的中间节点 - 快慢双指针（⼀定要画图分析 slow 的落点）
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        // 2. 把 slow 后⾯的部分给逆序 - 头插法
        ListNode head2 = new ListNode(0);
        ListNode cur = slow.next;
        slow.next = null; // 把两个链表分离
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = head2.next;
            head2.next = cur;
            cur = next;
        }
        // 3. 合并两个链表 - 双指针
        ListNode cur1 = head, cur2 = head2.next;
        ListNode ret = new ListNode(0);
        ListNode prev = ret;
        while (cur1 != null) {
            // 先放第⼀个链表
            prev.next = cur1;
            prev = cur1;
            cur1 = cur1.next;
            // 在合并第⼆个链表
            if (cur2 != null) {
                prev.next = cur2;
                prev = cur2;
                cur2 = cur2.next;
            }
        }
    }
}
